Connect Level Neighbors
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
Given the root of a binary tree, give every node a next pointer to the node immediately to its right on the same level. If a node is the last one on its level, its next pointer should be None.
The tree isn't guaranteed to be perfect. Some nodes may have only one child, or no children at all, at any level.
Return the root once every node's next pointer is set.
Input: root = [21, 14, 28, 7, 17, None, 35]
Output: [21 -> None], [14 -> 28 -> None], [7 -> 17 -> 35 -> None]
Notice 14 links straight to 28 even though it's the parent's other child, and 17 links to 35 even though 17 and 35 don't share a parent.
Input: root = [40, 25, None]
Output: [40 -> None], [25 -> None]
Each level only has one node, so every next pointer is None.
Input: root = [9, None, 12, None, None, None, 20]
Output: [9 -> None], [12 -> None], [20 -> None]
You might also hear this problem called “Populating Next Right Pointers in Each Node.”
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.